\relax 
\citation{mihail}
\citation{drw-jacm}
\citation{mihail}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{\thepage }}
\newlabel{sec:intro}{{1}{\thepage }}
\citation{mihail}
\citation{MatulaS90}
\citation{LovaszS90}
\citation{SpielmanT04}
\citation{LovaszS90}
\citation{SpielmanT04}
\citation{BBSB04}
\citation{ZS06}
\citation{LovaszS90}
\citation{SpielmanT04}
\citation{drw-jacm}
\citation{kempe}
\citation{JS89}
\citation{drw-jacm}
\citation{kempe}
\citation{PK09}
\citation{peleg}
\citation{peleg}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.1}Model and Definitions}{\thepage }}
\newlabel{sec:model}{{1.1}{\thepage }}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {1.1.1}Distributed Computing Model}{\thepage }}
\newlabel{sec:distmodel}{{1.1.1}{\thepage }}
\citation{AP09}
\citation{AroraRV04}
\citation{BenczurK96}
\citation{BhattL84}
\citation{DasSarmaGP09}
\citation{Karger00}
\citation{ManokaranNRS08}
\citation{SpielmanT04}
\citation{AndersenCL06}
\citation{SpielmanT04}
\citation{AndersenCL06}
\citation{DasSarmaGP09}
\citation{LovaszS90}
\citation{LovaszS93}
\citation{SpielmanT04}
\citation{Alon86}
\citation{Boppana87}
\citation{JerrumS88}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {1.1.2}Definitions}{\thepage }}
\newlabel{sec:def}{{1.1.2}{\thepage }}
\newlabel{def:conductance}{{1}{\thepage }}
\newlabel{def:balance}{{2}{\thepage }}
\newlabel{def:balance}{{3}{\thepage }}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.2}Problem Statement and Our Results}{\thepage }}
\newlabel{sec:results}{{1.2}{\thepage }}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {1.2.1}Problem Statement}{\thepage }}
\@writefile{toc}{\contentsline {subsubsection}{\numberline {1.2.2}Our Results}{\thepage }}
\newlabel{thm:algo1}{{1.1}{\thepage }}
\newlabel{thm:cluster}{{1.2}{\thepage }}
\newlabel{thm:lb}{{1.3}{\thepage }}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.3}Related Work}{\thepage }}
\newlabel{sec:related}{{1.3}{\thepage }}
\citation{LovaszS90}
\citation{LovaszS93}
\citation{SpielmanT04}
\citation{AndersenCL06}
\citation{DasSarmaGP09}
\citation{AndersenCL06}
\citation{SpielmanT04}
\citation{AroraRV04}
\citation{KannanVV04}
\citation{LeightonR99}
\citation{SimaS06}
\citation{LeightonR99}
\citation{AroraRV04}
\citation{AroraHK04}
\citation{AroraK07}
\citation{KhandekarRV06}
\citation{OrecchiaSVV08}
\citation{CzumajS10}
\citation{GoldreichR11}
\citation{KaleS11}
\citation{NachmiasS10}
\citation{mihail}
\citation{SpielmanT04}
\@writefile{toc}{\contentsline {section}{\numberline {2}A Distributed Algorithm for Sp-arse Cut}{\thepage }}
\newlabel{sec:sparse-cut}{{2}{\thepage }}
\citation{SpielmanT04}
\citation{SpielmanT04}
\citation{LovaszS93}
\citation{SpielmanT04}
\citation{DasSarmaGP09}
\citation{SpielmanT04}
\citation{LovaszS93}
\citation{DasSarmaGP09}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Estimating Random Walk Probability Distribution}{\thepage }}
\newlabel{sec:prob-estimate}{{2.1}{\thepage }}
\@writefile{loa}{\contentsline {algorithm}{\numberline {1}{\ignorespaces \sc  EstimateProbability}}{\thepage }}
\newlabel{alg:randomwalk}{{1}{\thepage }}
\newlabel{lem:probability-accuracy}{{2.1}{\thepage }}
\newlabel{lem:time-randomwalk}{{2.2}{\thepage }}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Computation of Sparse Cut}{\thepage }}
\newlabel{thm:conductance-estimate}{{2.3}{\thepage }}
\citation{topkis}
\citation{SpielmanT04}
\newlabel{lem:parallel-conductance}{{2.4}{\thepage }}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Node $j$ computes the number of its neighbors that are in the left side and right side of $j$ in the ordered vertex set $\pi $.}}{\thepage }}
\newlabel{fig:n-cut}{{1}{\thepage }}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.3}Description and Analysis of the Algorithm}{\thepage }}
\citation{SpielmanT04}
\@writefile{loa}{\contentsline {algorithm}{\numberline {2}{\ignorespaces \sc  SparseCut}}{\thepage }}
\newlabel{alg:sparsecut}{{2}{\thepage }}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.4}Time Complexity Analysis}{\thepage }}
\newlabel{lem:phase1-sc}{{2.5}{\thepage }}
\newlabel{lem:phase2-sc}{{2.6}{\thepage }}
\newlabel{thm:time-sparsecut}{{2.7}{\thepage }}
\citation{SpielmanT11}
\citation{AroraRV04}
\citation{Koutis14}
\citation{DasSarmaHKKNPPW12}
\citation{DasSarmaHKKNPPW12}
\citation{DasSarmaHKKNPPW12}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.5}Finding Local Cluster Set}{\thepage }}
\newlabel{sec:local-cluster}{{2.5}{\thepage }}
\@writefile{toc}{\contentsline {section}{\numberline {3}A Different Approach via Graph Sparsification}{\thepage }}
\newlabel{sec:different-approach}{{3}{\thepage }}
\@writefile{toc}{\contentsline {paragraph}{Running time:}{\thepage }}
\@writefile{toc}{\contentsline {section}{\numberline {4}Lower Bound}{\thepage }}
\newlabel{sec:lower-bound}{{4}{\thepage }}
\citation{mihail}
\bibstyle{abbrv}
\bibdata{Distributed-RW}
\bibcite{Alon86}{1}
\bibcite{AndersenCL06}{2}
\bibcite{AP09}{3}
\bibcite{AroraHK04}{4}
\bibcite{AroraK07}{5}
\bibcite{AroraRV04}{6}
\bibcite{BenczurK96}{7}
\bibcite{BhattL84}{8}
\bibcite{Boppana87}{9}
\bibcite{BBSB04}{10}
\bibcite{CzumajS10}{11}
\bibcite{DasSarmaGP09}{12}
\bibcite{DasSarmaHKKNPPW12}{13}
\bibcite{drw-jacm}{14}
\bibcite{mihail}{15}
\bibcite{GoldreichR11}{16}
\bibcite{JerrumS88}{17}
\bibcite{JS89}{18}
\bibcite{KaleS11}{19}
\bibcite{KannanVV04}{20}
\bibcite{Karger00}{21}
\bibcite{kempe}{22}
\bibcite{KhandekarRV06}{23}
\bibcite{Koutis14}{24}
\bibcite{LeightonR99}{25}
\bibcite{LovaszS90}{26}
\bibcite{LovaszS93}{27}
\@writefile{toc}{\contentsline {section}{\numberline {5}Conclusion}{\thepage }}
\newlabel{sec:conclusion}{{5}{\thepage }}
\@writefile{toc}{\contentsline {section}{\numberline {6}References}{\thepage }}
\bibcite{ManokaranNRS08}{28}
\bibcite{MatulaS90}{29}
\bibcite{NachmiasS10}{30}
\bibcite{OrecchiaSVV08}{31}
\bibcite{PK09}{32}
\bibcite{peleg}{33}
\bibcite{SimaS06}{34}
\bibcite{SpielmanT04}{35}
\bibcite{SpielmanT11}{36}
\bibcite{topkis}{37}
\bibcite{ZS06}{38}
